#include "d_list.h"

dl_node *
dl_node_create(elem_t e)
{
	dl_node * node = malloc(sizeof(dl_node));
	node->data = e;
	node->prev = 0;
	node->next = 0;

	return node;
}

void
dl_node_release(dl_node * node)
{
	free(node);
}

d_list
d_list_clone(const_d_list l)
{
	if (!l) {
		return 0;
	}

	dl_node * node = dl_node_create(l->data);
	d_list ret = node;
	dl_node * tail = node;
	l = l->next;
	while (l) {
		node = dl_node_create(l->data);
		node->prev = tail;
		tail->next = node;
		tail = node;
		l = l->next;
	}

	return ret;
}

void
d_list_release(d_list l)
{
	dl_node * node = 0;
	while (l) {
		node = l;
		l = l->next;
		dl_node_release(node);
	}
}

size_t
d_list_len(const_d_list l)
{
	size_t len = 0;
	while (l) {
		l = l->next;
		++len;
	}

	return len;
}

d_list
d_list_append(d_list * l, elem_t * p, size_t len)
{
	if (!len) {
		return *l;
	}

	if (!*l) {
		*l = dl_node_create(*p++);
		--len;
	}

	dl_node * node = *l;
	for (; node->next; node = node->next) {}

	for (; len; --len) {
		node->next = dl_node_create(*p++);
		node->next->prev = node;
		node = node->next;
	}

	return *l;
}

void d_list_display(const_d_list l)
{
	printf(" || ");
	while (l) {
		printf(" ==> %d ", l->data);
		l = l->next;
	}
	printf("\n");
}

int
d_list_get(const_d_list l, index_t i, elem_t * e)
{
	for (index_t ii = 0; ii < i && l; ++ii) {}
	return l ? (*e = l->data, 0) : -1;
}

index_t
d_list_locate(const_d_list l, elem_t e)
{
	for (index_t i = 0; l; ++i, l = l->next) {
		if (l->data == e) {
			return i;
		}
	}

	return -1;
}

dl_iterator
d_list_insert(dl_iterator it, elem_t e)
{
	dl_node * node = dl_node_create(e);
	node->next = it;
	node->prev = it->prev;
	node->prev->next = node;
	node->next->prev = node;

	return node;
}

dl_iterator
d_list_delete(dl_iterator it, elem_t * e)
{
	dl_node * node = it;
	node->next->prev = node->prev;
	node->prev->next = node->next;
	it = node->next;

	*e = node->data;

	return it;
}

d_list
d_list_sort(d_list * lp)
{
	d_list l = *lp;

	if (!l) {
		return 0;
	}

	dl_node * node = l;
	l = l->next;

	d_list ret = node;

	while (l) {
		node = l;
		l = l->next;

		dl_iterator it = ret;
		for (; it->next && it->next->data < node->data; it = it->next) {}
		node->next = it->next;
		node->prev = it;
		it->next = node;
		if (node->next) {
			node->next->prev = node;
		}
	}

	*lp = ret;

	return ret;
}

d_list
d_list_reverse(d_list * lp)
{
	d_list l = *lp;
	if (!l) {
		return 0;
	}

	dl_node * node = l;
	l = l->next;
	node->prev = 0;
	node->next = 0;

	d_list rl = node;

	while (l) {
		node = l;
		l = l->next;

		node->next = rl;
		rl->prev = node;
		rl = node;
	}

	*lp = rl;

	return rl;
}


